package 剑指offer;

public class 剑指Offer68II二叉树的最近公共祖先 {
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果root 等于p  或者  等于q, 直接返回root
        if (root == p || root == q) return root;
        //否则在这颗树中后续遍历节点
        lastOrder(root,p,q);
        return lca;
    }

    private boolean lastOrder(TreeNode root, TreeNode p, TreeNode q) {
        //如果树为空，直接返回false；
        if (root == null) return  false;
        //否则在左边子树中找p或者q，找到了任意一个，就说明左子树存在至少一个节点
        int left = lastOrder(root.left,p,q) ? 1 : 0;//找到了就将left置为1；
        int right = lastOrder(root.right,p,q) ? 1 : 0;//在右子树中找到了就说明右子树存在直晒一个
        int mid = (p == root || q == root) ? 1 : 0;//如果当前节点就为p，或者q，就说明根节点存在一个节点
        //如果在左子树，右子树，或者根节点中，有两个及以上的节点，就说明从改根节点出发，能够同时找到pq两个节点
        if (mid + left + right >= 2){
            lca = root;//那么从当前节点出发，就能找pq两节点，当前root就为pq的最近公共祖先。
        }
        //找到了一个就返回true，否则为false；
        return (mid + left + right) > 0;
    }
}
